package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/partition-array-for-maximum-sum/description/
 * @create 2025/9/5 22:13
 * @since JDK17
 */

public class Solution82 {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];  // 以i结尾最多可以分割的值
        for (int i = 1; i <= n; i++) {
            int val = arr[i - 1];   // 当前位置的值
            for (int j = i - 1; j > 0 && j >= i - k; j--) {
                dp[i] = Math.max(dp[i], dp[j] + (i - j) * val);
                if (j > 0) {
                    val = Math.max(val, arr[j - 1]);
                }
            }
        }
        return dp[n];
    }
}
